package main.leetcode.offer.firstround.from03to50;

import main.datastruc.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 32-II.从上到下打印二叉树
 *
 * <p>从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 *
 * <p>
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex32II {
    private List<List<Integer>> res;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(4);
        System.out.println(new ex32II().levelOrder(root));
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        res = new ArrayList<>();
        helper(root, 0);
        return res;
    }

    private void helper(TreeNode root, int level) {
        if (root == null) return;
        if (level + 1 > res.size()) res.add(new ArrayList<>());
        res.get(level).add(root.val);
        if (root.left != null) helper(root.left, level + 1);
        if (root.right != null) helper(root.right, level + 1);
    }
}
